#include <bits/stdc++.h>

using namespace std;

// 合并 K 个升序链表
// 测试链接：https://leetcode.cn/problems/merge-k-sorted-lists/

// 不需要提交这个类
struct ListNode 
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

// 提交这个类即可
class Solution 
{
private:
    ListNode* merge(ListNode* head1, ListNode* head2)
    {
        if(!head1 || !head2) return head1 ? head1 : head2;

        ListNode *newHead = head1->val <= head2->val ? head1 : head2;
        ListNode *tail = newHead;
        head1->val <= head2->val ? head1 = head1->next : head2 = head2->next;
        while(head1 && head2)
        {
            if(head1->val < head2->val)
            {
                tail->next = head1;
                head1 = head1->next;
            }
            else
            {
                tail->next = head2;
                head2 = head2->next;
            }
            tail = tail->next;
        }
        tail->next = head1 ? head1 : head2;
        return newHead;
    }

    ListNode* mergeKLists(vector<ListNode*>& lists, int left, int right)
    {
        if(left == right) return lists[left];
        if(left > right) return nullptr;
        
        int mid = left + (right - left) / 2;
        ListNode* l = mergeKLists(lists, left, mid);
        ListNode* r = mergeKLists(lists, mid + 1, right);
        return merge(l, r);
    }

public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        return mergeKLists(lists, 0, lists.size() - 1);
    }
};


// 提交这个类即可
class Solution 
{
private:
    struct cmp
    {
        bool operator()(const ListNode* l1, const ListNode* l2)
        {
            return l1->val > l2->val;
        }
    };

public:
    ListNode* mergeKLists(vector<ListNode*>& lists) 
    {
        if(lists.empty()) return nullptr;
        // 创建一个小根堆
        priority_queue<ListNode*, vector<ListNode*>, cmp> heap;

        // 让所有的头结点进入小根堆
        for(auto l : lists)
        {
            if(l) heap.push(l);
        }
        // 没有节点，直接返回 null
        if(heap.empty()) return nullptr;

        // 合并 k 个有序链表
        ListNode* newHead = heap.top();
        heap.pop();
        if(newHead->next) heap.push(newHead->next);
        ListNode* tail = newHead;
        while(!heap.empty())
        {
            ListNode* t = heap.top();
            heap.pop();
            tail->next = t;
            tail = t;
            if(t->next) heap.push(t->next);
        }
        return newHead;
    }
};